const q = [];       //queue

const WHITE = 0;    //没有被访问过
const GRAY = 1;     //访问过，但是它的所有相邻节点没有访问完    
const BLACK = 2;    //访问完成，所有相邻节点都访问到了

const color = {};   //表示各个点的状态
const d = {};       //表示从source到所有连通点的距离， 搜索路径不需要用到这个
const pi = {};      //广度优先树, 就是存储的路径

let adj = {};       //邻接表


// 初始化：
// adj, color, d, pi
function init(nodes, edges) {
    adj = createAdj(edges);
    for (let node of nodes) {
        color[node] = WHITE;
        d[node] = Infinity;
        pi[node] = null;
    }
}


// 搜索路径
function searchPath(source, target) {
    let u = null;
    init(nodes, edges);                 //初始化
    color[source] = GRAY;               //source节点首先变灰色
    d[source] = 0;                      //source节点距离自己为0
    pi[source] = null;                  //source节点没有父节点
    q.push(source);                     //source节点入队列
    while (q.length) {                  //队列不空
        u = q.shift();                  //出队列一个节点
        for (let v of adj[u]) {         //搜索这个节点所有的相邻节点
            if (color[v] === WHITE) {   //如果这个节点没有被访问过(颜色是白色)
                color[v] = GRAY;        //颜色变灰
                d[v] = d[u] + 1;        //距离是父节点的距离+1
                pi[v] = u;              //设置父节点
                q.push(v);              //入队列
            }
        }
        color[u] = BLACK;               //所有相邻节点都访问完了
    }
    return displayPath(pi, source, target);    //根据广度优先树生成路径
}


// 创建邻接表
function createAdj(edges) {
    const adj = {};
    for (let { source, target } of edges) {
        adj[source] === undefined ? (adj[source] = [target]) : adj[source].push(target);
        adj[target] === undefined ? (adj[target] = [source]) : adj[target].push(source);
    }
    return adj;
}


// 现实路径
function displayPath(pi, source, target) {
    let path = [target];
    let pre = pi[target];
    while (pre !== source) {
        path.push(pre);
        pre = pi[pre];
    }
    path.push(pre);
    return path.reverse();
}



// 检测生成邻接表的算法是否错误
// function checkRepeat(adj) {
//     for ([s, e] of Object.entries(adj)) {
//         let set = new Set(e);
//         if (set.size !== e.length) {
//             console.log(`reapeat : ${s}`)
//         }
//     }
// }

